# 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
# 输入: "babad"
# 输出: "bab"
# 注意: "aba" 也是一个有效答案。
# 输入: "cbbd"
# 输出: "bb"


def longestPalindrome(s):
    len_str = len(s)
    result = ""
    for piece in enumerate(s):
        i = 0
        if len(result) + piece[0] >= len_str:
            break
        while True:
            str1 = s[piece[0]:len_str - i]
            if piece[0] == 0:
                str2 = s[len_str - i - 1::-1]
            else:
                str2 = s[len_str - i - 1:piece[0] - 1:-1]
            if str1 == str2:
                if len(str1) > len(result):
                    result = str1
                break
            i += 1
    return result


def manacher(s):
    # 预处理
    s = '#'+'#'.join(s)+'#'
    RL = [0]*len(s)
    MaxRight = 0
    pos = 0
    MaxLen = 0
    for i in range(len(s)):
        if i < MaxRight:
            RL[i] = min(RL[2*pos-i], MaxRight-i)
        else:
            RL[i] = 1
        # 尝试扩展，注意处理边界
        while (i-RL[i] >= 0) and (i+RL[i] < len(s)) and (s[i-RL[i]] == s[i+RL[i]]):
            RL[i] += 1
        # 更新MaxRight,pos
        if RL[i]+i-1 > MaxRight:
            MaxRight = RL[i]+i-1
            pos = i
        # 更新最长回文串的长度
        MaxLen = max(MaxLen, RL[i])
    return MaxLen-1

print(longestPalindrome("cbbd"))

